/************************************************************
* DS_MULTI_MAP.HPP                                12.12.2007
*
* .
************************************************************/

namespace impl {

/**************************************************************************
* MAP_CONST_ITERATOR()                                                    *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP_CONST_ITERATOR<K, V, H, C, A>::MAP_CONST_ITERATOR(const MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> & multiIter)
   : container(multiIter.container)
   , item(multiIter.item)
   , index()
{
   if (item != NULL) {
      index = container->GetHash(item->key) % container->data.Length();
   }
}

#ifndef _RETAIL
/**************************************************************************
* MAP_CONST_ITERATOR()                                                    *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP_CONST_ITERATOR<K, V, H, C, A>::MAP_CONST_ITERATOR(const BEGIN_HELPER<MAP_ITERATOR<K, V, H, C, A> > & helper)
   : container(helper.iter.container)
   , item(helper.iter.item)
   , index(helper.iter.index)
{}
#endif

/**************************************************************************
* MAP_ITERATOR()                                                          *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP_ITERATOR<K, V, H, C, A>::MAP_ITERATOR(const MAP_MULTI_ITERATOR<K, V, H, C, A> & multiIter)
   : MAP_CONST_ITERATOR<K, V, H, C, A>(static_cast<const MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> &> (multiIter))
{}

/*************************************************************
* H, C> & MULTI_MAP_ITERATOR<K, V, H, C, A>::operator ++()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP_CONST_ITERATOR<K, V, H, C, A> & MAP_CONST_ITERATOR<K, V, H, C, A>::operator ++ (void)
{
#if !defined _AP_PS3
#pragma warning(disable : 4311)
	// PS3 seems to get no benefit from prefetching, and in fact
	// seems to slow it down a little, and generates a million 
	// warnings due to the offsetof trick, so leave it out.
	//osPrefetch(item, (int)(&((item_type*)0)->next));
#pragma warning(default : 4311)
#endif

	if (item == NULL) {
		STRONG_ASSERT(!"Trying to increment iterator that's already done");
		return *this;
	}

	if (item->next != NULL) {
		item = item->next;
		return *this;
	}

	if (container->data.IsEmpty()) {
		STRONG_ASSERT(!"Invalid iterator: reference to empty map");
		return const_cast<MAP_CONST_ITERATOR &> (*this) = MAP_CONST_ITERATOR();
	}

	do {
		++index;
	} while (index < container->data.Length() && container->data[index] == NULL);

	// end reached
	if (index >= container->data.Length()) {
		return const_cast<MAP_CONST_ITERATOR &> (*this) = MAP_CONST_ITERATOR();
	}

	item = container->data[index];
	return *this;
}

/*************************************************************
* H, C> & MULTI_MAP_ITERATOR<K, V, H, C, A>::operator ++()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP_CONST_MULTI_ITERATOR<K, V, H, C, A> & MAP_CONST_MULTI_ITERATOR<K, V, H, C, A>::operator ++ (void)
{
#if !defined _AP_PS3
#pragma warning(disable : 4311)
	// PS3 seems to get no benefit from prefetching, and in fact
	// seems to slow it down a little, and generates a million 
	// warnings due to the offsetof trick, so leave it out.
	osPrefetch(item, (int)(&((item_type*)0)->next));
#pragma warning(default : 4311)
#endif

	if (item == NULL) {
		STRONG_ASSERT(!"Trying to increment iterator that's already done");
		return *this;
	}

   key_type key_value = item->key;
   while (item->next != NULL) {
	   item = item->next;
      if (map_type::cmp_type::equals(item->key, key_value)) {
		   return *this;
	   }
   }

	if (container->data.IsEmpty()) {
		STRONG_ASSERT(!"Invalid iterator: reference to empty map");
		return const_cast<MAP_CONST_MULTI_ITERATOR &> (*this) = MAP_CONST_MULTI_ITERATOR();
	}

	item = NULL;

	return *this;
}

/*************************************************************
* H, C> & MULTI_MAP_ITERATOR<K, V, H, C, A>::operator ==()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
bool MAP_CONST_ITERATOR<K, V, H, C, A>::operator == (const MAP_CONST_ITERATOR & p) const
{
	return container == p.container
		&& item      == p.item;
}

/*************************************************************
* V, H, C>::operator *()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
const typename MAP<K, V, H, C, A>::value_type & MAP_CONST_ITERATOR<K, V, H, C, A>::operator * (void) const
{
	STRONG_ASSERT(item != NULL);
	return item->value;
}

/*************************************************************
* MAP<K, V, H, C, A>::key_type & MULTI_MAP_ITERATOR<K, V, H, C, A>::key()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
const typename MAP<K, V, H, C, A>::key_type & MAP_CONST_ITERATOR<K, V, H, C, A>::key(void) const
{
	STRONG_ASSERT(item != NULL);
	return item->key;
}

/*************************************************************
* V, H, C>::value_type & MULTI_MAP_ITERATOR<K, V, H, C, A>::value()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
const typename MAP<K, V, H, C, A>::value_type & MAP_CONST_ITERATOR<K, V, H, C, A>::value(void) const
{
	STRONG_ASSERT(item != NULL);
	return item->value;
}

} // namespace impl

/*************************************************************
* H, C>::MAP()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::GenHashes(void)
{
	a = ds::FindPrime(10 + m3dRandInt());
	b = m3dRandInt();
}

/*************************************************************
* H, C>::MAP()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP<K, V, H, C, A>::MAP(apCL _cl)
: count(0)
#ifdef AP_USE_MEM_STAT 
, data(_cl), allocator(_cl), cl(_cl)
#endif
{
	GenHashes();
}

/*************************************************************
* H, C>::MAP()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
MAP<K, V, H, C, A>::MAP(const MAP<K, V, H, C, A> & p)
   : count(0)
#ifdef AP_USE_MEM_STAT 
   , data(p.cl), allocator(p.cl), cl(p.cl)
#endif
{
	GenHashes();

	HashResize(p.HashSize());
   for (const_iterator iter = p.Begin(); !iter.IsDone(); ++iter) {
		InsertNew(iter.key(), iter.value());
	}
}

/*************************************************************
* V, H, C>::operator =()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::operator = (const MAP & p)
{
	if (this == &p) {
		return ;
	}

	this->~MAP();
	new (this) MAP(p);
}

/**************************************************************************
* MAP::GetHash()
*
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
template <class T0>
int MAP<K, V, H, C, A>::GetHash(const T0 & key) const
{
	int val = hash_type::hash(key, a, b);
   STRONG_ASSERT1(val >= 0 && (unsigned) val < ds::BIG_PRIME, val);
	return val;
}

/*************************************************************
* MAP::TryToResize()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
bool MAP<K, V, H, C, A>::TryToResize(int depth)
{
	if (data.IsEmpty()) {
		HashResize(DEFAULT_SIZE);
		return true;
	}

	ASSERT(depth < 2 * MAXDEPTH_2);
	if (count > MAXDATA   * data.Length()
		||  count > MAXDATA_2 * data.Length() && depth > MAXDEPTH
		||  count > MAXDATA_3 * data.Length() && depth > MAXDEPTH_2) {

			if (depth > MAXDEPTH) {
				GenHashes();
			}

			HashResize(FindPrime(data.Length() * SIZE_MULT));
			return true;
	}

	return false;
}

/*************************************************************
* MAP::Resize()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::HashResize(int size)
{
	if (!CheckPrime(size)) {
		size = FindPrime(size);
		if ((UINT) size == a) {
			size = FindPrime(size + DEFAULT_SIZE);
		}
	}

	dsVECTOR<ITEM *> newData(size, NULL);

	for (int i=0; i<data.Length(); ++i) {
		if (data[i] != NULL) {
			ITEM * cur = data[i];
			while (cur != NULL) {
				ITEM * next = cur->next;
				int index = GetHash(cur->key) % newData.Length();
				cur->next = newData[index];
				newData[index] = cur;
				cur = next;
			}
		}
	}

	data.Swap(newData);
}

/*************************************************************
* MAP::Insert()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::Insert(ITEM *& item, const key_type & key, const value_type & value)
{
	dummy_type * ptr = allocator.Alloc();
	ITEM * newItem = new (ptr) ITEM(key, value);
	newItem->next  = item;

	item = newItem;
}

/*************************************************************
* MAP::Insert()
* 
* returns true if element with same key already exists
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K,V,H,C,A>::result_type MAP<K, V, H, C, A>::Insert(const key_type & key, const value_type & value)
{
	if (data.IsEmpty()) {
		data.Resize(DEFAULT_SIZE, NULL);
	}

	int index = GetHash(key) % data.Length();

	if (data[index] == NULL) {
		++count;

		Insert(data[index], key, value);
		return result_type(iterator(*this, *data[index], index), false);
	}

	// try to find item with same key
	int depth = 1;
	ITEM * item = data[index];
	while (item->next && cmp_type::equals(item->key, key) == false) {
		item = item->next;
		++depth;
	}

	// if has item with same key, just rewrite value (and return true)
	if (cmp_type::equals(item->key, key)) {
		item->value = value;
		return result_type(iterator(*this, *item, index), true);
	}

	// update element count
	++count;

	Insert(item->next, key, value);

	item = item->next;

	// check if hashmap must be resized
	if (TryToResize(depth)) {
		return result_type(iterator(*this, *item, GetHash(key) % data.Length()), false);
	}

	return result_type(iterator(*this, *item, index), false);
}

/*************************************************************
* MAP::Insert()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::iterator MAP<K, V, H, C, A>::InsertNew(const key_type & key, const value_type & value)
{
	if (data.IsEmpty()) {
		data.Resize(DEFAULT_SIZE, NULL);
	}

	int index = GetHash(key) % data.Length();

	// if ds::MAP used as multimap - just add new element to beginning of the list
	++count;
	Insert(data[index], key, value);
	return iterator(*this, *data[index], index);
}

/*************************************************************
* H, C>::iterator MAP<K, V, H, C, A>::Find()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::iterator MAP<K, V, H, C, A>::Find(const key_type & key)
{
	if (data.IsEmpty()) {
		return iterator();
	}

	// calc key's hash
	int index = GetHash(key) % data.Length();
	if (data[index] == NULL) {
		return iterator();
	}

	// check item list
	ITEM * cur = data[index];
	while (cur != NULL && cmp_type::equals(cur->key, key) == false) {
		cur = cur->next;
	}
	if (cur == NULL) {
		return iterator();
	}

	return iterator(*this, *cur, index);
}

/*************************************************************
* H, C>::iterator MAP<K, V, H, C, A>::Find()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
template <class K0>
typename MAP<K, V, H, C, A>::iterator MAP<K, V, H, C, A>::Find(const K0 & key)
{
	if (data.IsEmpty()) {
		return iterator();
	}

	// calc key's hash
	int index = abs(GetHash(key) % data.Length());
	if (data[index] == NULL) {
		return iterator();
	}

	// check item list
	ITEM * cur = data[index];
	while (cur != NULL && cmp_type::equals(cur->key, key) == false) {
		cur = cur->next;
	}
	if (cur == NULL) {
		return iterator();
	}

	return iterator(*this, *cur, index);
}

/*************************************************************
* V, H, C>::Find()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
bool MAP<K, V, H, C, A>::Contains(const key_type & key, value_type * value /*= NULL*/) const
{
	if (data.IsEmpty()) {
		return false;
	}

	// calc key's hash
	int index = GetHash(key) % data.Length();
	if (data[index] == NULL) {
		return false;
	}

	// check item list
	ITEM * cur = data[index];
	while (cur != NULL && cmp_type::equals(cur->key, key) == false) {
		cur = cur->next;
	}
	if (cur == NULL) {
		return false;
	}

	if (value) {
		*value = cur->value;
	}
	return true;
}

/*************************************************************
* V, H, C>::iterator MULTI_MAP_ITERATOR<K, V, H, C, A>::Begin()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
DS_BEGIN_HELPER(typename MAP<K _ V _ H _ C _ A>::iterator) MAP<K, V, H, C, A>::Begin(void)
{
	int index = 0;
	while (index < data.Length() && data[index] == NULL) {
		++index;
	}

	if (index >= data.Length()) {
		return iterator();
	}

	return iterator(*this, *data[index], index);
}

/*************************************************************
* V, H, C>::Clear()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::Clear(void)
{
	for (int i=0; i<data.Length(); ++i) {
		if (data[i] == NULL) {
			continue;
		}

		ITEM * cur = data[i];
		while (cur != NULL) {
			ITEM * next = cur->next;
			Delete(cur);
			cur = next;
		}
	}
	data.Clear();
	count = 0;
}

/*************************************************************
* V, H, C>::Free()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::Free(void) {
   Clear();
   data.Free();
   allocator.Free();
}

/*************************************************************
* V, H, C>::iterator MAP<K, V, H, C, A>::Erase()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::iterator MAP<K, V, H, C, A>::Erase(iterator iter)
{
	// check if iter == end()
	if (iter.IsDone()) {
		return iterator();
	}

	// store next iterator
	iterator next = iter;
	++next;

	if (data.IsEmpty()) {
		STRONG_ASSERT(!"Invalid iterator: references to empty map");
		return iterator();
	}

	// find item's parent
	int index = GetHash(iter.key()) % data.Length();

	ITEM ** parent = &data[index];
	ITEM * cur = data[index];
	while (cur != NULL && cur != iter.item) {
		parent = &(*parent)->next;
		cur = cur->next;
	}

	if (cur == NULL || *parent == NULL) {
		STRONG_ASSERT(!"Invalid iterator: data corrupted");
		return iterator();
	}

	// update element count
	--count;

	*parent = cur->next;
	Delete(cur);
	return next;
}

/*************************************************************
* V, H, C>::multi_iterator MAP<K, V, H, C, A>::Erase()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::multi_iterator MAP<K, V, H, C, A>::Erase(multi_iterator iter)
{
	// check if iter == end()
	if (iter.IsDone()) {
		return iterator();
	}

	// store next iterator
	multi_iterator next = iter;
	++next;

	if (data.IsEmpty()) {
		STRONG_ASSERT(!"Invalid iterator: references to empty map");
		return iterator();
	}

	// find item's parent
	int index = GetHash(iter.key()) % data.Length();

	ITEM ** parent = &data[index];
	ITEM * cur = data[index];
	while (cur != NULL && cur != iter.item) {
		parent = &(*parent)->next;
		cur = cur->next;
	}

	if (cur == NULL || *parent == NULL) {
		STRONG_ASSERT(!"Invalid iterator: data corrupted");
		return iterator();
	}

	// update element count
	--count;

	*parent = cur->next;
	Delete(cur);
	return next;
}

/*************************************************************
* V, H, C>::Erase()
* 
*************************************************************/
template <class K, class V, class H, class C, template <class> class A>
int MAP<K, V, H, C, A>::Erase(const key_type & key)
{
	if (data.IsEmpty()) {
		return 0;
	}

	int res = 0;

	// try to find item with this key
	int index = GetHash(key) % data.Length();
	ITEM ** parent = &data[index];
	ITEM * cur = data[index];

	for (;;) {
		while (cur != NULL && cmp_type::equals(cur->key, key) == false) {
			parent = &(*parent)->next;
			cur = cur->next;
		}

		if (cur == NULL || *parent == NULL) {
			return res;
		}

		// update element count
		--count;
		++res;

		*parent = cur->next;
		Delete(cur);

		cur = *parent;
	}
}

/**************************************************************************
* V, H, C, A>::iterator MAP<K, V, H, C, A>::FindInsert()                  *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::iterator MAP<K, V, H, C, A>::FindInsert(const key_type & key, const value_type & value /* = value_type */)
{
	iterator iter = Find(key);
	if (!iter.IsDone()) {
		return iter;
	}

	return InsertNew(key, value);
}

/**************************************************************************
* V, H, C, A>::Swap()                                                     *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
void MAP<K, V, H, C, A>::Swap(MAP<K, V, H, C> & p)
{
	dsSwap(count, p.count);
	data.Swap(p.data);
	allocator.Swap(p.allocator);
}

#ifdef __PLUGIN__
template <class K, class V, class H, class C, template <class> class A>
struct MAP<K, V, H, C, A>::APPEND_HELPER {
   APPEND_HELPER(MAP<K, V, H, C, A> * map, const K & key)
      : map(map), key(key)
   {}

   MAP<K, V, H, C, A> * const    map;
   K                             key;

   struct APPEND_HELPER_2 {
      APPEND_HELPER_2(MAP<K, V, H, C, A> * map)
         : map(map)
      {}

      template <class K0>
      APPEND_HELPER operator , (const K0 & key) {
         return APPEND_HELPER(map, key);
      }

      MAP<K, V, H, C, A> * const map;
   };

   template <class V0>
   APPEND_HELPER_2 operator , (const V0 & value) {
      map->Insert(key, value);
      return APPEND_HELPER_2(map);
   }
};

/**************************************************************************
* V, H, C, A>::operator += ()                                             *
*                                                                         *
**************************************************************************/
template <class K, class V, class H, class C, template <class> class A>
typename MAP<K, V, H, C, A>::APPEND_HELPER MAP<K, V, H, C, A>::operator += (const K & key) {
   return APPEND_HELPER(this, key);
}
#endif

//
// End-of-file DS_MULTI_MAP.HPP
//
